1. Field of the Invention
The invention relates to Field Programmable Gate Arrays (FPGAs). More particularly, the invention relates to a method for synthesizing priority encoders into carry logic in an FPGA.
2. Description of the Background Art
Programmable integrated circuits (ICs) are a well-known type of integrated circuit that may be programmed by a user to perform specified logic functions. (The term "programmable ICs" as used herein includes but is not limited to FPGAs, mask programmable devices such as Application Specific ICs (ASICs), Programmable Logic Devices (PLDs), and devices in which only a portion of the logic is programmable.) One type of programmable IC, the field programmable gate array (FPGA), typically includes an array of configurable logic blocks (CLBs) surrounded by a ring of programmable input/output blocks (IOBs). The CLBs and IOBs are interconnected by a programmable interconnect structure. The CLBs, IOBs, and interconnect structure are typically programmed by loading a stream of configuration data (bitstream) into internal configuration memory cells that define how the CLBS, IOBs, and interconnect structure are configured. The configuration data may be read from memory (e.g., an external PROM) or written into the FPGA by an external device. The collective states of the individual memory cells then determine the function of the FPGA.
A CLB typically includes one or more function generators (often implemented as lookup tables, or LUTs), and one or more registers that can optionally be used to register the LUT outputs. Some CLBs also include carry logic that is used to implement arithmetic functions such as adders, subtractors, counters, and multipliers. Implementing logic using carry chains can be faster, sometimes much faster, than implementing the equivalent logic in LUTs. The speed of a carry chain depends on the number of bits in the carry chain (among other factors). The speed of the equivalent logic implemented as LUTs depends on the number of levels of logic (i.e., the number of LUTs on the slowest path) required to implement the carry function. However, the use of carry logic imposes placement constraints in that the ordering of the bits in the FPGA implementing a user's function is set by the carry chain.
Two forms of design entry are common: schematic entry and Hardware Description Languages (HDLs) such as Verilog and VHDL. When schematic entry is used, the designer can specify the exact implementation desired for his circuit. However, when HDL code is used, the circuit is described by its logical function. Synthesis software then translates the logical function into specific logic targeted for a specified FPGA. Although circuit elements can be manually instantiated in HDL code, this method is avoided since it is labor-intensive and the code can typically only be targeted to a specific programmable IC architecture.
Well-known synthesis tools such as those distributed by Synopsys, Inc., of Mountain View, Calif., recognize arithmetic functions in the HDL code and implement these functions using carry logic. However, other types of statements used in HDL code are not so implemented, even when the method that is used results in a much slower circuit. For example, Synopsys synthesis tools recognize two constructs currently implemented using LUTs: priority encoder constructs and multiplexer constructs. These two constructs are sometimes implemented differently, although they are based on similar HDL statements.
A priority encoder construct is inferred when a priority determination statement has been used in the Verilog code. Verilog supports two types of priority determination statements, if/else statements and case/switch statements. An if/else statement is a well-known programming concept, although the syntax varies in different HDLs. In Verilog, an if/else statement takes the form:
______________________________________ if (test0) do.sub.-- result0; else if (test1) do.sub.-- result1; else if (test2) do.sub.-- result2; . . . else do.sub.-- default.sub.-- result; end ______________________________________
The else if and else portions of an if/else statement are optional. If none of the tests returns True, the default result is performed.
A case/switch statement has a similar function, but uses a different syntax. In Verilog, a case/switch statement takes the form:
______________________________________ case (variable) test0 : do.sub.-- result0; test1 : do.sub.-- result1; . . . default : do.sub.-- default.sub.-- result; end ______________________________________
The default portion of a case/switch statement is optional. In a case/switch statement, the case portion defines a variable; and each test compares the value of the variable to a given test value. If the variable has none of the tested values, the default result is performed.
A priority encoder selects from among two or more results based on a sequential series of "tests", as shown in the exemplary Verilog code of FIG. 1. Once a test has been passed, the specified result is selected, and any remaining tests are not performed. (Hence the name "priority encoder".) For example, if the test in line 9 of FIG. 1 (a[0] .vertline. .vertline. b[0]) returns False (i.e., if neither a[0] nor b[0] is True), the test in line 11 (a[1] && b[1]) is performed. If this second test returns True (i.e., if both a[1] and b[1] are True), then output "dout" is set to "din[1]" as specified in line 12.
A multiplexer construct is inferred when a parallel case/switch statement is used. A parallel case/switch statement is a statement in which the person writing the code specifies that only one of the tests will be True at a given time. (This specification is typically done by adding a comment, where the format of the comment varies depending on the synthesis software used.) Therefore, although synthesis software typically treats multiplexers and priority encoders as two separate constructs, a multiplexer is a limited form of a priority encoder, where only one of the tests can be True at a given time.
Using priority determination statements can greatly simplify the task of entering a logic description of a circuit, but present synthesis methods typically implement such statements as logic that spans many levels of LUTs, thereby limiting the performance of the resulting design. It would be desirable for synthesis tools to implement priority determination statements as carry logic, when doing so results in a faster design.